Leetcode 322.零钱兑换

题目描述：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1
2

输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2

输入：coins = [1], amount = 0
输出：0

示例 4：

1
2

输入：coins = [1], amount = 1
输出：1

示例 5：

1
2

输入：coins = [1], amount = 2
输出：2

提示：

• $1 <= coins.length <= 12$
• $1 <= coins[i] <= 2^{31} - 1$
• $0 <= amount <= 10^4$

链接：

https://leetcode-cn.com/problems/coin-change

题目分析

  我看到这道题的时候就想到了两种思路。一种是贪心法，我们知道想要使得硬币组合的总数少，那肯定是使用面值越大的越多越好，我们可以从硬币面值最大的开始使用 DFS 进行搜索。当然这样也可能导致解不存在而需要回溯，比如 amount = 21 而 coins = [2, 9, 10]，如果我们贪心的使用了两个面值为 10 的硬币就会导致找不到解，这个时候还要进行回溯，减少大面值硬币的个数。另一种情况是 DFS 找到的第一个解也不一定是最优解，比如 amount = 14 而 coins = [1, 7, 10]，DFS 找到的第一个解应该是 10+1+1+1 而最优解其实是 7+7。这样的情况导致我们即使是使用贪心法，最后也得遍历所有的可能情况，所以也不能做到很快，而且回溯的过程比较麻烦，也不够简洁。
  另一种比较暴力的方法就是动态规划。我们令 dp[i] 表示凑成 i 所需要的最少硬币数，则 dp[i] 可以通过 dp[i-j] + 1（其中 j 是单枚硬币的面值）获得。我们只需要遍历所有的硬币面值，找到使得 dp 值最小的那个即可。题目中没有说 coins 已经排序，为了加速遍历过程，我们先对其进行排序，这样在寻找最小值的过程中，到了 j > i 的情况就可以直接停止。而我们最后要求的答案就是 dp[amount]。
  我们知道边界值是 dp[0] = 0，然后就可以从 1 到 amount 进行遍历。对于那些无法凑成的金额该怎么处理呢？可以直接赋为最大值 INT_MAX 吗？答案是不可以的，因为我们在状态转移的时候会对其加 1，超过了上限就会变为负数，这个时候寻找最小值就会出问题。注意到 amount 的值并不会很大，那么我们可以直接将初始值赋为 amount + 1，就表示无法凑成，因为硬币最小面值为 1，如果可以凑成一定不会超过 amount 个。这样这个数继续增大也不会出问题。最后返回结果的时候判断 dp[amount] 是否会大于 amount 即可。（当然，我们也可以先判断 dp[i-j] 是否可以凑成然后再进行状态转移，这样初始值可以赋为 -1，最后直接返回结果，也是可行的。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(), coins.end());
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < coins.size() && coins[j] <= i; j++){
                dp[i] = min(dp[i], dp[i-coins[j]] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

  时间复杂度：$O(ac)$，其中 $a、c$ 分别表示 amount 的值和 coins 的长度。这是因为我们需要进行 amount 次状态转移，而每次状态转移的时间复杂度是 $O(c)$。这里因为 coins 的长度很小，所以排序的时间复杂度忽略。
  空间复杂度：$O(a)$，其中 $a$ 表示 amount 的值。也即保存动态规划状态的数组大小。